package leetcode_1100;

import helpclass.TreeNode;

/**
 *@author 周杨 
 *BinarySearchTreeToGreaterSumTree_1038 题目没看太懂
 *describe:AC 100%
 *2019年5月18日 上午11:09
 */
public class BinarySearchTreeToGreaterSumTree_1038 {
	private int lower = 0;
    public TreeNode bstToGst(TreeNode root) {
        int sum = sum(root);
        preorder(root, sum);
        return root;
    }
    
    private int sum(TreeNode root) {
        int r = 0;
        if (root != null) {
            r += sum(root.left);
            r += sum(root.right);
            r += root.val;
        }
        return r;
    }
    
    private void preorder(TreeNode root, int sum) {
        if (root != null) {
            preorder(root.left, sum);
            int t = root.val;
            root.val = sum - lower;
            lower += t;
            preorder(root.right, sum);
        }
    }
}
